<!doctype html>
<html>
	<head>
		<meta charset="utf-8">
		<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no">

		<title>State Machines Battlefield - Naive vs STL vs Boost</title>

		<link rel="stylesheet" href="reveal.js/css/reveal.css">
    <link rel="stylesheet" href="reveal.js/css/theme/league.css" id="theme">
    <link rel="stylesheet" href="extensions/plugin/line-numbers/line-numbers.css">
    <link rel="stylesheet" href="extensions/css/highlight-styles/zenburn.css">
    <link rel="stylesheet" href="extensions/css/custom.css">

		<script>
			var link = document.createElement( 'link' );
			link.rel = 'stylesheet';
			link.type = 'text/css';
			link.href = window.location.search.match( /print-pdf/gi ) ? 'reveal.js/css/print/pdf.css' : 'reveal.js/css/print/paper.css';
			document.getElementsByTagName( 'head' )[0].appendChild( link );

      function set_address(self, remote, local) {
        if (window.location.search.match("local")) {
          self.href = local;
        } else {
          self.href = remote;
        }
      }
		</script>

		<meta name="description" content="State Machines Battlefield - Naive vs STL vs Boost">
		<meta name="author" content="Kris Jusiak">
		<meta name="apple-mobile-web-app-capable" content="yes">
		<meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
	</head>

	<body>
		<div class="reveal">
			<div class="slides">
          <section data-markdown=""
                   data-separator="^====+$"
                   data-separator-vertical="^----+$">
					<script type="text/template">
#### CppCon 2018

## State Machines Battlefield
## Naive vs STL vs Boost

Kris Jusiak, Quantlab Financial

#### [kris@jusiak.net](mailto:kris@jusiak.net) | [@krisjusiak](https://twitter.com/krisjusiak) | [linkedin.com/in/kris-jusiak](https://www.linkedin.com/in/kris-jusiak)

==============================================================================

<!--### Outline-->

<!--* `Problem / Motivation`-->
<!--* `State Machine`-->
<!--* `Solutions`-->
  <!--* `Naive`-->
  <!--* `STL`-->
  <!--* `Boost`-->
<!--* `Benchmarks`-->
<!--* `Summary`-->

<!--==============================================================================-->

### Problem / Motivation

```gherkin
Feature: Connection # BDD style
```
<!-- .element: class="fragment" -->

---

```gherkin
  Scenario: Establish connection
```
<!-- .element: class="fragment" -->

```gherkin
    Given I don't have a connection
```
<!-- .element: class="fragment" -->

```gherkin
     When I receive a request to connect
```
<!-- .element: class="fragment" -->

```gherkin
     Then I should try to establish the connection
```
<!-- .element: class="fragment" -->

```gherkin
     When I receive an established acknowledgement
```
<!-- .element: class="fragment" -->

```gherkin
     Then I should have been connected
```
<!-- .element: class="fragment" -->

---

```gherkin
  Scenario: Disconnect
  ...
```
<!-- .element: class="fragment" -->

----

### Problem / Motivation

> What's the

* `most readable`
<!-- .element: class="fragment" -->
* `most maintainable`
<!-- .element: class="fragment" -->
* `most efficient`
<!-- .element: class="fragment" -->

> way to satisfy/implement `Connection` requirements?

==============================================================================

### State Machine - Unified Modeling Language - 2.5

> State Machine - Connection
<!-- .element: class="fragment" data-fragment-index="1" -->

<table>
<tr>
<td style="vertical-align: middle">
<pre><code class="gherkin">Feature: Connection
 Scenario: Connect
  ...

 Scenario: Disconnect
  ...

 Scenario: ...
  ...
</code></pre>
</td>
<!-- .element: class="fragment" -->
<td>
<img src="images/connection.png" style="width: 100%; background:none; border:none; box-shadow:none;" />
<!-- .element: class="fragment" -->
</td>
</tr>
</table>

#### https://www.omg.org/spec/UML/2.5.1/PDF
<!-- .element: class="fragment" data-fragment-index="1" -->

==============================================================================

### Solutions

![solutions](images/solutions.png)
<!-- .element: class="fragment" -->

----

### Common - Implementation

#### Events
<!-- .element: class="fragment" data-fragment-index="1" -->

```cpp
struct connect{};
struct established{};
struct ping{};
struct disconnect{};
struct timeout{};
```
<!-- .element: class="fragment" data-fragment-index="1" -->

#### Guards
<!-- .element: class="fragment" data-fragment-index="2" -->

```cpp
constexpr auto is_valid      = [](auto const& event) { return true; };
```
<!-- .element: class="fragment" data-fragment-index="2" -->

#### Actions
<!-- .element: class="fragment" data-fragment-index="3" -->

```cpp
constexpr auto establish     = []{ std::puts("establish"); };
constexpr auto close         = []{ std::puts("close"); };
constexpr auto reset_timeout = []{ std::puts("reset_timeout"); };
```
<!-- .element: class="fragment" data-fragment-index="3" -->

----

## Naive

>C++98 features

----

#### Naive - If/Else - Implementation

```cpp
class Connection {
  // Implicit states using booleans
  bool disconnected = true, connected = false, connecting = false;
```
<!-- .element: class="fragment" -->

```cpp
  constexpr void process_event(connect const&) {
    if (disconnected) {
      establish();
      connected = disconnected = false; // Just in case reset it all!
      connecting = true; // Set the new state
    }
  }
```
<!-- .element: class="fragment" -->

```cpp
  constexpr void process_event(ping const& event) {
    if (connected and is_valid(event)) {
      reset_timeout();
    } // Stay in the current state
  }
```
<!-- .element: class="fragment" -->

----

##### Naive - If/Else - Full Example

<!--<div style="margin-left:-10%; width:120%">-->
![gb_if_else](images/gb_if_else.png)
<!--</div>-->

#### https://godbolt.org/z/APHwnc

----

#### Naive - If/Else - Summary

* (+) Inlined (gcc/clang)
<!-- .element: class="fragment" -->
* (+) No heap usage
<!-- .element: class="fragment" -->
* (~) Small-ish memory footprint
<!-- .element: class="fragment" -->
    * ```sizeof(Connection) == 3b```
* (-) Hard to reuse
<!-- .element: class="fragment" -->

<img src="images/if.jpg" style="width: 50%; background:none; border:none; box-shadow:none;" />
<!-- .element: class="fragment" -->

----

#### Naive - Switch/Enum - Implementation

```cpp
class Connection {
  // Only one state can be active
  enum class State : char { DISCONNECTED,
                            CONNECTING,
                            CONNECTED } state = DISCONNECTED;
```
<!-- .element: class="fragment" -->

```cpp
  constexpr void process_event(connect const&) {
    switch (state) { // Handle current state
      default: break;
      case State::DISCONNECTED:
        establish(); state = State::CONNECTING; break;
                  // Set the new state
    }
  }
```
<!-- .element: class="fragment" -->

```cpp
  constexpr void process_event(ping const& event) {
    switch (state) {
      default: break;
      case State::CONNECTED:
        if (is_valid(event)) { reset_timeout(); }
        break; // Stay in the current state
    }
  }
```
<!-- .element: class="fragment" -->

----

#### Naive - Switch/Enum - Full Example

<!--<div style="margin-left:-10%; width:120%">-->
![gb](images/gb_switch.png)
<!--</div>-->

#### https://godbolt.org/z/NM_-oY

----

#### Naive - Switch/Enum - Summary

* (+) Inlined (gcc/clang)
<!-- .element: class="fragment" -->
* (+) Small memory footprint
<!-- .element: class="fragment" -->
    * ```sizeof(Connection) == 1b```
* (+) No heap usage
<!-- .element: class="fragment" -->
* (-) Hard to reuse
<!-- .element: class="fragment" -->

<img src="images/debug.jpg" style="width: 40%; background:none; border:none; box-shadow:none;" />
<!-- .element: class="fragment" -->

----

#### Inheritance / State pattern - Implementation

```cpp
struct State {
  virtual ~State() noexcept = default;
  virtual void process_event(connect const&) = 0;
  virtual void process_event(ping const&) = 0;
  virtual void process_event(established const&) = 0;
  virtual void process_event(timeout const&) = 0;
  virtual void process_event(disconnect const&) = 0;
};
```
<!-- .element: class="fragment" -->

----

#### Inheritance / State pattern - Implementation

```cpp
struct Disconnected : State {
  Connection& connection;

  void process_event(connect const&) override final {
    establish();
    connection.change_state<Connecting>();
  }
};
```
<!-- .element: class="fragment" -->

```cpp
struct Connected : State {
  Connection& connection;

  void process_event(ping const& event) override final {
    if (is_valid(event)) {
      reset_timeout();
    }
  }

  // ...
};
```
<!-- .element: class="fragment" -->

----

#### Inheritance / State pattern - Full Example

<!--<div style="margin-left:-10%; width:120%">-->
![gb](images/gb_inheritance.png)
<!--</div>-->

#### https://godbolt.org/z/dui-ar

----

#### Inheritance / State pattern - Summary

* (+) Easy to extend/reuse (object oriented)
<!-- .element: class="fragment" -->
* (~) High-ish memory footprint
<!-- .element: class="fragment" -->
* (-) Heap usage / dynamic allocations
<!-- .element: class="fragment" -->
* (-) Not inlined/devirtualized (even with final)
<!-- .element: class="fragment" -->

<img src="images/slow.jpg" style="width: 55%; background:none; border:none; box-shadow:none;" />
<!-- .element: class="fragment" -->

----

## STL

> C++17 / C++20 Standard Template Library

----

#### std::variant - Implementation

```cpp
class Connection {
  struct Disconnected { }; // May have additional data
  struct Connecting { };
  struct Connected { };

  // Only one active state
  std::variant<Disconnected, Connecting, Connected> state
    = Disconnected{};
```
<!-- .element: class="fragment" -->

```cpp
  constexpr void process_event(connect const&) {
    std::visit(overload{ // Choose one of the following...
      [&](Disconnected) { establish(); state = Connecting{}; },
       [](auto)         { } // No changes...
    }, state);
  }
```
<!-- .element: class="fragment" -->

```cpp
  void process_event(ping const& event) {
    if (std::get_if<Connected>(&state) and is_valid(event)) {
      reset_timeout();
    } // Stay in the current state
  }
```
<!-- .element: class="fragment" -->

----

#### std::variant - Full Example

<!--<div style="margin-left:-10%; width:120%">-->
![gb](images/gb_variant.png)
<!--</div>-->

#### https://godbolt.org/z/oY2FBl

----

#### std::variant - Summary

* (+) Small/efficient memory footprint
<!-- .element: class="fragment" -->
  * ```cpp
    Disconnect { };
    Connecting { connection_id id{}; };
    Connected  { connection_id id{};
                 time last_ping{}; };
    ```
* (+) Integrates well with std::expected/static exceptions
<!-- .element: class="fragment" -->
  * ```cpp
    return Error{"timeout"};
    ```
* (~) Inlined (clang only)
<!-- .element: class="fragment" -->
* (-) Hard to reuse (Similar to switch/enum)
<!-- .element: class="fragment" -->

----

#### Coroutines / loop - Implementation

```cpp
auto Connection = [](auto& in) {
  for (;;) { // Wait for an event... -> Disconnected
    if (auto [event, data] = co_await in; event == connect) {
      establish();
```
<!-- .element: class="fragment" data-fragment-index="1" -->

```cpp
      for (;;) { // -> Connecting
        if (auto [event, data] = co_await in; event == established) {
```
<!-- .element: class="fragment" data-fragment-index="2" -->

```cpp
          for (;;) { // -> Connected
            switch (auto [event, data] = co_await in; event) {
              case ping:
                if (is_valid(data)) { reset_timeout(); continue; }
              case timeout: establish(); break;
              case disconnect: close(); goto end;
            }
          }
        }
```
<!-- .element: class="fragment"  -->

```cpp
      } end:;
```
<!-- .element: class="fragment" data-fragment-index="2" -->

```cpp
    } // Otherwise go back to co_await and suspend...
  }
};
```
<!-- .element: class="fragment" data-fragment-index="1" -->

----

#### Coroutines / loop - Full Example

<!--<div style="margin-left:-10%; width:120%">-->
![gb](images/gb_coroutines_loop.png)
<!--</div>-->

#### https://godbolt.org/z/P3zaNt

----

#### Coroutines / loop - Summary

* (+) Structured code using C++ features
<!-- .element: class="fragment"  -->
* (+) Easily to switch between Async/Sync versions
<!-- .element: class="fragment"  -->
* (~) Learning curve (different way of thinking)
<!-- .element: class="fragment"  -->
* (~) Requires heap (heap elision / devirtualization)
<!-- .element: class="fragment"  -->
* (~) Implicit states (position in the function)
<!-- .element: class="fragment"  -->
* (-) Events require a common type
<!-- .element: class="fragment"  -->
* (-) Weird usage of infinite loops
<!-- .element: class="fragment"  -->

----

#### Coroutines / goto - Implementation

```cpp
auto Connection = [](auto& in) {
  for (;;) {
    disconnected: // State is represented by a position in the function
    if (auto [event, data] = co_await in; event == connect) {
      establish();
```
<!-- .element: class="fragment" data-fragment-index="1" -->

```cpp
      connecting:
      if (auto [event, data] = co_await in; event == established) {
```
<!-- .element: class="fragment" data-fragment-index="2" -->

```cpp
        connected:
        switch (auto [event, data] = co_await in; event) {
          case ping:
            if (is_valid(data)) { reset_timeout(); goto connected; }
          case timeout: establish();
            goto connecting; // Set the new state
          case disconnect:
            close(); goto disconnected;
        }
```
<!-- .element: class="fragment" -->

```cpp
      }
```
<!-- .element: class="fragment" data-fragment-index="2" -->

```
} } };
```
<!-- .element: class="fragment" data-fragment-index="1" -->

----

#### Coroutines / goto - Full Example

<!--<div style="margin-left:-10%; width:120%">-->
![gb](images/gb_coroutines_goto.png)
<!--</div>-->

#### https://godbolt.org/z/BjuHL9

----

#### Coroutines / goto - Summary

* (+) No infinite loops
<!-- .element: class="fragment" -->
* (~) Explicit states
<!-- .element: class="fragment" -->
* (-) GOTO!
<!-- .element: class="fragment" -->

![goto](images/goto.png)
<!-- .element: class="fragment" -->

----

#### Coroutines / functions / variant - Implementation

```cpp
auto disconnected() {
  for (;;) { // Wait for the connect event...
```
<!-- .element: class="fragment" data-fragment-index="1" -->

```cpp
    if (auto const event = co_await in; std::get_if<connect>(&event)) {
      establish(); co_return connecting(); // Set the new state
    }
```
<!-- .element: class="fragment" data-fragment-index="2" -->

```cpp
} }
```
<!-- .element: class="fragment" data-fragment-index="1" -->

```cpp
auto connected() {
  for (;;) {  // Wait for the ping event...
   auto const event = co_await in;
```
<!-- .element: class="fragment" data-fragment-index="4" -->

```cpp
   if (std::get_if<ping>(&event) and is_valid(std::get<ping>(event))) {
     reset_timeout();
   } else if (std::get_if<timeout>(&event)) {
     establish(); co_return connecting();
   } else if (std::get_if<disconnect>(&event)) {
     close();     co_return disconnected();
   }
```
<!-- .element: class="fragment" data-fragment-index="5" -->

```cpp
} }
```
<!-- .element: class="fragment" data-fragment-index="4" -->

----

#### Coroutines / functions / variant - Full Example

<!--<div style="margin-left:-10%; width:120%">-->
![gb](images/gb_coroutines_variant.png)
<!--</div>-->

#### https://godbolt.org/z/tCiWKh

----

#### Coroutines / functions / variant - Summary

* (+) Easier to add/follow new states/behaviour
<!-- .element: class="fragment" -->
* (+) Type safe events
<!-- .element: class="fragment" -->

<img src="images/fancy.jpg" style="width: 55%; background:none; border:none; box-shadow:none;" />
<!-- .element: class="fragment" -->

----

## Boost

![boost_libraries](images/boost_libraries.png)
<!-- .element: class="fragment" data-fragment-index="1" -->

Disclaimer: [Boost].SML is not an official Boost library
<!-- .element: class="fragment" data-fragment-index="1" -->

----

#### Boost.Statechart - Implementation

#### Events
<!-- .element: class="fragment" data-fragment-index="1" -->

```cpp
struct connect     : sc::event<connect> {};
struct ping        : sc::event<ping> {};
struct established : sc::event<established> {};
struct timeout     : sc::event<timeout> {};
struct disconnect  : sc::event<disconnect> {};
```
<!-- .element: class="fragment" data-fragment-index="1" -->

#### Actions/Guards
<!-- .element: class="fragment" data-fragment-index="2" -->

```cpp
struct Connection : sc::state_machine<Connection, Disconnected> {
  template<class TEvent>
  void establish(TEvent const&)   { std::puts("establish"); }
  void reset_timeout(ping const&) { std::puts("reset_timeout"); }
  void close(disconnect const&)   { std::puts("close"); }
  bool is_valid(ping const&)      { return true; }
};
```
<!-- .element: class="fragment" data-fragment-index="2" -->

----

#### Boost.Statechart - Implementation

```cpp
struct Disconnected : sc::simple_state<Disconnected, Connection> {
  using reactions = mpl::list<
    sc::transition<connect, Connecting,
                   Connection, &Connection::establish>>;
};
```
<!-- .element: class="fragment"  -->

```cpp
struct Connected : sc::simple_state<Connected, Connection> {
  using reactions = mpl::list<
    sc::transition<timeout, Connecting,
                   Connection, &Connection::establish>,
    sc::transition<disconnect, Disconnected,
                   Connection, &Connection::close>,
    sc::custom_reaction<ping>
  >;
```
<!-- .element: class="fragment"  -->

```cpp
  sc::result react(ping const& event) {
    if (context<Connection>().is_valid(event)) {
      context<Connection>().reset_timeout(event);
    }
    return discard_event();
  }
};
```
<!-- .element: class="fragment"  -->

----

#### Boost.Statechart - Full Example

<!--<div style="margin-left:-10%; width:120%">-->
![gb](images/gb_boost_statechart.png)
<!--</div>-->

#### https://godbolt.org/z/NN8UyH

----

#### Boost.Statechart - Summary

* (+) UML-1.5 features
<!-- .element: class="fragment"  -->
* (~) Learning curve (Similar to State Pattern)
<!-- .element: class="fragment"  -->
* (-) Dynamic allocations
<!-- .element: class="fragment"  -->
* (-) Dynamic dispatch
<!-- .element: class="fragment"  -->
* (-) High memory footprint
<!-- .element: class="fragment"  -->

----

#### Boost.MSM / eUML - Implementation

#### Events
<!-- .element: class="fragment" data-fragment-index="1" -->

```cpp
BOOST_MSM_EUML_EVENT(connect)
BOOST_MSM_EUML_EVENT(ping)
BOOST_MSM_EUML_EVENT(established)
BOOST_MSM_EUML_EVENT(timeout)
BOOST_MSM_EUML_EVENT(disconnect)
```
<!-- .element: class="fragment" data-fragment-index="1" -->

#### States
<!-- .element: class="fragment" data-fragment-index="2" -->

```cpp
BOOST_MSM_EUML_STATE((), Disconnected)
BOOST_MSM_EUML_STATE((), Connecting)
BOOST_MSM_EUML_STATE((), Connected)
```
<!-- .element: class="fragment" data-fragment-index="2" -->

----

#### Boost.MSM / eUML - Implementation

#### Actions
<!-- .element: class="fragment" data-fragment-index="1" -->

```cpp
BOOST_MSM_EUML_ACTION(establish){
  template <class FSM, class EVT, class SourceState, class TargetState>
  void operator()(EVT const&, FSM &, SourceState &, TargetState &) {
    std::puts("establish");
  }
};
```
<!-- .element: class="fragment" data-fragment-index="1" -->

#### Guards
<!-- .element: class="fragment" data-fragment-index="2" -->

```cpp
BOOST_MSM_EUML_ACTION(is_valid) {
  template <class FSM, class EVT, class SourceState, class TargetState>
  auto operator()(EVT const&, FSM&, SourceState&, TargetState&) {
    return true;
  }
};
```
<!-- .element: class="fragment" data-fragment-index="2" -->

----

#### Boost.MSM / eUML - Implementation

```cpp
BOOST_MSM_EUML_TRANSITION_TABLE((
  Connecting   == Disconnected + connect / establish,
  Connected    == Connecting   + established,
                  Connected    + ping [ is_valid ] / reset_timeout,
  Connecting   == Connected    + timeout / establish,
  Disconnected == Connected    + disconnect / close
),
transition_table)
```
<!-- .element: class="fragment" -->

```cpp
BOOST_MSM_EUML_DECLARE_STATE_MACHINE
  ((transition_table, init_ << Disconnected), ConnectionImpl)
```
<!-- .element: class="fragment" -->

```cpp
using Connection = msm::back::state_machine<ConnectionImpl>;
```
<!-- .element: class="fragment" -->

----

#### Boost.MSM / eUML - Full Example

<!--<div style="margin-left:-10%; width:120%">-->
![gb](images/gb_boost_msm.png)
<!--</div>-->

#### https://godbolt.org/z/nVTV0J

----

#### Boost.MSM / eUML - Summary

* (+) Declarative/Expressive (UML transition)
<!-- .element: class="fragment" -->
* (+) Dispatch O(1) - jump table
<!-- .element: class="fragment" -->
* (+) UML-2.0 features
<!-- .element: class="fragment" -->
* (+) Small memory footprint
<!-- .element: class="fragment" -->
* (~) Learning curve
<!-- .element: class="fragment" -->
* (~) DSL based
<!-- .element: class="fragment" -->
* (-) Macro based
<!-- .element: class="fragment" -->
* (-) Slow compilation times
<!-- .element: class="fragment" -->
  * Timeouts in the Compiler-Explorer
* (-) Error messages
<!-- .element: class="fragment" -->

----

#### [Boost].SML - Implementation

```cpp
sml::sm connection = []{
  using namespace sml;
  return transition_table{
    * "Disconnected"_s + event<connect> / establish   = "Connecting"_s,
      "Connecting"_s   + event<established>           = "Connected"_s,
      "Connected"_s    + event<ping> [ is_valid ] / reset_timeout,
      "Connected"_s    + event<timeout> / establish   = "Connecting"_s,
      "Connected"_s    + event<disconnect> / close    = "Disconnected"_s
  };
};
```
<!-- .element: class="fragment" -->

<!--<img src="images/transition_table_sml.png" style="width: 155%; background:none; border:none; box-shadow:none;" />-->
<!-- .element: class="fragment" -->

----

#### [Boost].SML - performance Tuning

> Don't pay for what you don't use!
<!-- .element: class="fragment" -->

<img src="images/perf.jpg" style="width: 50%; background:none; border:none; box-shadow:none;" />

----

#### Dispatch policy changes event dispatching strategy

| Name | Policy | Default |
| - | - |
| Jump Table | `jump_table` | `gcc < 8.0`  |
| Nested Switch | `switch`  | `gcc >= 8.0` |
| If/Else | `branch` | `clang` |
| Fold expressions | `fold_expr` | `gcc/clang with C++17` |

----

#### [Boost].SML / dispatch policy - If/Else

```cpp
template <class TMappings, // back-end -> generated transitions
          auto N,
          class TState,
          class... TStates,
          class TEvent>
constexpr auto dispatch(state_t &current_state, TEvent const &event) {
```
<!-- .element: class="fragment" data-fragment-index="1" -->

```cpp
  if constexpr(sizeof...(TStates...) > 0) {
    return current_state == N
     ? TMappings<TState>::execute(event)
     : dispatch<TMappings, N + 1, TStates...>(current_state, event);
   }
```
<!-- .element: class="fragment" -->

```cpp
}
```
<!-- .element: class="fragment" data-fragment-index="1" -->

----

#### [Boost].SML / dispatch policy - If/Else

<!--<div style="margin-left:-10%; width:120%">-->
![gb](images/gb_boost_sml_branch.png)
<!--</div>-->

#### https://godbolt.org/z/Dsn1PF

----

#### [Boost].SML / dispatch policy - Switch

```cpp
template <class TMappings, // back-end -> generated transitions
          auto N = 0,
          class TState,
          class... TStates,
          class TEvent>
constexpr auto dispatch(state_t &current_state, TEvent const &event) {
```
<!-- .element: class="fragment" data-fragment-index="1" -->

```cpp
  if constexpr(sizeof...(TStates...) > 0) {
    switch (current_state) {
      default: return dispatch<TMappings, N + 1, TStates...>(
                        current_state, event);
      case N:  return TMappings<TState>::execute(event);
    }
  }
```
<!-- .element: class="fragment" -->

```cpp
}
```
<!-- .element: class="fragment" data-fragment-index="1" -->

----

#### [Boost].SML / dispatch policy - Switch

<!--<div style="margin-left:-10%; width:120%">-->
![gb](images/gb_boost_sml_switch.png)
<!--</div>-->

#### https://godbolt.org/z/AKmGiy

----

#### [Boost].SML / dispatch policy - Jump Table

```cpp
template <class TMappings, // back-end -> generated transitions
          class... TStates,
          class TEvent>
constexpr auto dispatch(state_t &current_state, TEvent const &event) {
```
<!-- .element: class="fragment" data-fragment-index="1" -->

```cpp
  using dispatch_table_t = bool (*)(TEvent const&);

  constexpr static dispatch_table_t dispatch_table[] = {
    &TMappings<TStates>::template execute<TEvent>...
  };

  return dispatch_table[current_state](event);
```
<!-- .element: class="fragment" -->

```cpp
}
```
<!-- .element: class="fragment" data-fragment-index="1" -->

----

#### [Boost].SML / dispatch policy - Jump Table

<!--<div style="margin-left:-10%; width:120%">-->
![gb](images/gb_boost_sml_jump_table.png)
<!--</div>-->

#### https://godbolt.org/z/lvjiX9

----

#### [Boost].SML / dispatch policy - Fold Expressions (C++17)

```cpp
template <class TMappings, // back-end -> generated transitions
          auto... Ns,
          class... TStates,
          class TEvent>
constexpr auto dispatch(state_t &current_state, TEvent const &event) {
```
<!-- .element: class="fragment" data-fragment-index="1" -->

```cpp
  static_assert(sizeof...(TStates) == sizeof...(Ns));

  return ((
    current_state == Ns
    ? TMappings<TStates>::execute(event)
    : false
  ) or ...);
```
<!-- .element: class="fragment" -->

```cpp
}
```
<!-- .element: class="fragment" data-fragment-index="1" -->

----

#### [Boost].SML / dispatch policy - Fold Expressions (C++17)

<!--<div style="margin-left:-10%; width:120%">-->
![gb](images/gb_boost_sml_fold_expr.png)
<!--</div>-->

#### https://godbolt.org/z/V_b7nM

----

#### [Boost].SML - Summary

* (+) Declarative/Expressive (UML transition)
<!-- .element: class="fragment" -->
* (+) Customizable (At compile time)
<!-- .element: class="fragment" -->
* (+) Inlined / Dispatch O(1)
<!-- .element: class="fragment" -->
* (+) Fast compilation times
<!-- .element: class="fragment" -->
* (+) UML-2.5 features
<!-- .element: class="fragment" -->
<!-- .element: class="fragment" -->
* (+) Minimal memory footprint
<!-- .element: class="fragment" -->
  * ```sizeof(Connection) == 1b```
* (~) Learning curve
<!-- .element: class="fragment" -->
* (~) DSL based
<!-- .element: class="fragment" -->

----

#### Solutions - Summary

![solutions_summary](images/solutions_summary.png)
<!-- .element: class="fragment" data-fragment-index="1" -->
<img src="images/solutions_summary_legend.png" style="width: 65%; background:none; border:none; box-shadow:none;" />
<!-- .element: class="fragment" data-fragment-index="1" -->

==============================================================================

### Benchmarks

----

#### Environment / Setup


```cpp
const auto action/guard = []{
  asm volatile("" : : : "memory");
};
```
<!-- .element: class="fragment" -->

```cpp
int main() {
  constexpr auto size = 1'000'000;
  std::array events = rand_events<size>();

  Connection connection{};
  for (auto i = 0; i < size; ++i) {
    process_event(events[i]);
  }
}
```
<!-- .element: class="fragment" -->

```sh
$CXX -std=c++2a      # clang-7.0.0/gcc-8.2
     -stdlib=libc++  # clang-7.0.0
     -fcoroutines-ts # clang-7.0.0
     -O3 -march=native -flto -fno-exceptions -DNDEBUG
     -I boost_1_68_0
```
<!-- .element: class="fragment" -->

----

#### Benchmarks - Lines of code (LOC)

![loc](images/performance_lines-of-code.png)

----

#### Benchmarks - ASM lines

![asm_lines](images/performance_asm-lines.png)

----

#### Benchmarks - Run-time performance - time / Release

![performance_release](images/performance_time[s]_release.png)

----

#### Benchmarks - Run-time performance - Instructions per cycle / Release

![performance_instruction-per-cycle_release-misses_release](images/performance_instruction-per-cycle_release.png)

----

#### Benchmarks - Run-time performance - branches / Release

![performance_branches_release](images/performance_branches_release.png)

----

#### Benchmarks - Run-time performance - branch misses / Release

![performance_branch-misses_release](images/performance_branch-misses_release.png)

----

#### Benchmarks - Compilation time / Debug

![compilation_time_debug](images/compilation_time[s]_debug.png)

----

#### Benchmarks - Compilation time / Release

![compilation_time_release](images/compilation_time[s]_release.png)

----

#### Benchmarks - Executable Size / Debug

![executable_size_debug](images/executable_size[kb]_debug.png)

----

#### Benchmarks - Executable Size / Release

![executable_size_release](images/executable_size[kb]_release.png)

==============================================================================

<!--### Summary-->

<!--* #### State machines are expressive way to represent the application flow-->
<!--[> .element: class="fragment" <]-->

<!--* #### There are different ways of implementing state machines in C++ with different trade-offs-->
<!--[> .element: class="fragment" <]-->

<!--* #### State Machines are more than just simple transitions [UML-2.5](http://www.omg.org/spec/UML/2.5/)-->
<!--[> .element: class="fragment" <]-->

<!--* ##### Leveraging Zero-cost libraries can boost the design and/or performance-->
<!--[> .element: class="fragment" <]-->

<!--==============================================================================-->

### Let's embrace zero-cost State Machine libraries!

| | |
| ------- | ------------- |
| Benchmarks | <a href="https://github.com/boost-experimental/sml/tree/master/benchmark/connection" >https://github.com/boost-experimental/sml/<br />tree/master/benchmark/connection</a> |
| Slides | http://boost-experimental.github.io/sml/cppcon-2018 |

-

#### [kris@jusiak.net](mailto:kris@jusiak.net) | [@krisjusiak](https://twitter.com/krisjusiak) | [linkedin.com/in/kris-jusiak](https://www.linkedin.com/in/kris-jusiak)
					</script>
				</section>

			</div>
		</div>

		<script src="reveal.js/lib/js/head.min.js"></script>
		<script src="reveal.js/js/reveal.js"></script>

		<script>

			// Full list of configuration options available at:
			// https://github.com/hakimel/reveal.js#configuration
			Reveal.initialize({

        // Display controls in the bottom right corner
        controls: true,

        // Display a presentation progress bar
        progress: true,

        // Display the page number of the current slide
        slideNumber: true,

        // Push each slide change to the browser history
        history: true,

        // Enable keyboard shortcuts for navigation
        keyboard: true,

        // Enable the slide overview mode
        overview: true,

        // Vertical centering of slides
        center: true,

        // Enables touch navigation on devices with touch input
        touch: true,

        // Loop the presentation
        loop: false,

        // Change the presentation direction to be RTL
        rtl: false,

        // Turns fragments on and off globally
        fragments: true,

        // Flags if the presentation is running in an embedded mode,
        // i.e. contained within a limited portion of the screen
        embedded: false,

        // Flags if we should show a help overlay when the questionmark
        // key is pressed
        help: true,

        // Flags if speaker notes should be visible to all viewers
        showNotes: false,

        // Number of milliseconds between automatically proceeding to the
        // next slide, disabled when set to 0, this value can be overwritten
        // by using a data-autoslide attribute on your slides
        autoSlide: 0,

        // Stop auto-sliding after user input
        autoSlideStoppable: true,

        // Enable slide navigation via mouse wheel
        mouseWheel: true,

        // Hides the address bar on mobile devices
        hideAddressBar: true,

        // Opens links in an iframe preview overlay
        previewLinks: true,

        // Transition style
        transition: 'convex', // none/fade/slide/convex/concave/zoom

        // Transition speed
        transitionSpeed: 'default', // default/fast/slow

        // Transition style for full page slide backgrounds
        backgroundTransition: 'default', // none/fade/slide/convex/concave/zoom

        // Number of slides away from the current that are visible
        viewDistance: 3,

        // Parallax background image
        parallaxBackgroundImage: '', // e.g. "'https://s3.amazonaws.com/hakim-static/reveal-js/reveal-parallax-1.jpg'"

        // Parallax background size
        parallaxBackgroundSize: '', // CSS syntax, e.g. "2100px 900px"

        // Number of pixels to move the parallax background per slide
        // - Calculated automatically unless specified
        // - Set to 0 to disable movement along an axis
        parallaxBackgroundHorizontal: null,
        parallaxBackgroundVertical: null,

				// Optional reveal.js plugins
				dependencies: [
					{ src: 'reveal.js/lib/js/classList.js', condition: function() { return !document.body.classList; } },
					{ src: 'reveal.js/plugin/markdown/marked.js', condition: function() { return !!document.querySelector( '[data-markdown]' ); } },
					{ src: 'reveal.js/plugin/markdown/markdown.js', condition: function() { return !!document.querySelector( '[data-markdown]' ); } },
					{ src: 'reveal.js/plugin/highlight/highlight.js', async: true, callback: function() { hljs.initHighlightingOnLoad(); } },
					{ src: 'reveal.js/plugin/zoom-js/zoom.js', async: true },
					{ src: 'reveal.js/plugin/notes/notes.js', async: true },
          { src: 'extensions/plugin/line-numbers/line-numbers.js' }
				]
			});
		</script>
	</body>
</html>
